LeetCode Solutions

Appearance

1547. 切棍子的最小成本 ​

为保证权益，题目请参考 1547. 切棍子的最小成本(From LeetCode).

解决方案1 ​

说明 ​

针对本问题，首先可以分析每次切割会造成什么后果。可以发现，分割后形成了两个独立且与父问题相似的子问题，因此，为避免重复计算，我们可以考虑通过动态规划或缓存的方式优化。

首先,为了对cuts有个全面的认知，对cuts进行排序并对两侧分别加入边缘长度0和n，即cuts=[0]+sorted(cuts)+[n]。

我们可以理解dp[i][j]为第i段线段和第￥j$段线段完全结合的需要的代价，然后可以有如下公式。

dp[i][j]=maxz∈(i,j−1)(dp[i][z]+dp[z+1][j])+(cuts[j+1]−cuts[i])

Python ​

python
from typing import List

# Old Version
# class Solution:
#     def minCost(self, n: int, cuts: List[int]) -> int:
#         cuts_num = len(cuts)
#         cuts = [0] + sorted(cuts) + [n]
#         dp = [[0 for _ in range(cuts_num + 1)] for _ in range(cuts_num + 1)]

#         for i in range(cuts_num + 1):
#             for j in range(cuts_num + 1):
#                 if i == 0:
#                     continue
#                 if j + i > cuts_num:
#                     continue
#                 dp[j][j + i] = min(
#                     [dp[j][z] + dp[z + 1][j + i] for z in range(j, j + i)]
#                 )
#                 dp[j][j + i] += cuts[j + i + 1] - cuts[j]

#         return dp[0][cuts_num]


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cuts_num = len(cuts)
        cuts = [0] + sorted(cuts) + [n]
        dp = [[0 for _ in range(cuts_num + 1)] for _ in range(cuts_num + 1)]

        for i in range(1, cuts_num + 1):
            for j in range(cuts_num - i, -1, -1):
                if j + i > cuts_num:
                    continue
                dp[j][j + i] = min(
                    [dp[j][z] + dp[z + 1][j + i] for z in range(j, j + i)]
                )
                dp[j][j + i] += cuts[j + i + 1] - cuts[j]

        return dp[0][cuts_num]


so = Solution()
print(so.minCost(7, [1, 3, 4, 5]))